/*
 * @Author: scl
 * @Date: 2023-08-03 14:34:13
 * @LastEditTime: 2023-08-03 22:11:12
 * @Description: file content
 */
/*
 * @lc app=leetcode.cn id=101 lang=typescript
 *
 * [101] 对称二叉树
 *
 * https://leetcode.cn/problems/symmetric-tree/description/
 *
 * algorithms
 * Easy (58.90%)
 * Likes:    2487
 * Dislikes: 0
 * Total Accepted:    866.5K
 * Total Submissions: 1.5M
 * Testcase Example:  '[1,2,2,3,4,4,3]'
 *
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 树中节点数目在范围 [1, 1000] 内
 * -100 <= Node.val <= 100
 * 
 * 
 * 
 * 
 * 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
*class TreeNode {
*    val: number
*    left: TreeNode | null
*    right: TreeNode | null
*    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
*        this.val = (val === undefined ? 0 : val)
*        this.left = (left === undefined ? null : left)
*        this.right = (right === undefined ? null : right)
*    }
*}
*/

function isSymmetric(root: TreeNode | null): boolean {
    let curr1: TreeNode = root.left, curr2: TreeNode = root.right
    if (!curr1 && !curr2) return true;
    else if (!(curr1 && curr2)) return false;
    else if (curr1.val != curr2.val) return false;
    else {
        let stack1: Array<TreeNode> = new Array(1).fill(curr1), stack2: TreeNode[] = new Array(1).fill(curr2)
        //中序遍历
        while (stack1.length > 0) {
            curr1 = stack1.pop()
            curr2 = stack2.pop()
            if (!curr1.left && !curr2.right) { }
            else if (curr1.left && !curr2.right || !curr1.left && curr2.right) {
                return false
            } else if (curr1.left?.val != curr2.right?.val) {
                return false
            } else {
                stack1.push(curr1.left)
                stack2.push(curr2.right)
            }
            if (!curr2.left && !curr1.right) { }
            else if (curr2.left && !curr1.right || !curr2.left && curr1.right) {
                return false
            } else if (curr2.left?.val != curr1.right?.val) {
                return false
            } else {
                stack2.push(curr2.left)
                stack1.push(curr1.right)
            }

        }
        return true
    }

};
// @lc code=end

